<?php
/**
 * php是支持查找array_keys(),array_search()
 * 二分查找
 **/
$sortArr = [1,2,3,4,5,6,7,8,9,10];


$key = search($sortArr, 2);
var_dump($key);

/**
 * 已经排序的数组,查到首个就返回key == array_search()
 * 先确认中间索引的值,使用while 数组的开始位置和结束位置实现类似递归的效果
 * 元素个数为n
 * 最好的情况1次就查到的
 * 最坏的情况每一次都没有查到,最后一次比对是只有个元素
 * n/2  (n/2-1)/2=n/4-1/2 n/2^3-1/2^2-1/2 .... n/2^k-(1/2^k-1+...1/2)=1
 * k就是次数 n=2^(k+1) k=log2(n)-1 近似于k=log2(n)
 **/
function search($sortArr, $v)
{
	$n = count($sortArr);
	$low = 0;
	$high = $n-1;
	while ($low <= $high) {
		$key= intval(($low+$high)/2);
     	if ($v < $sortArr[$key]) {
			$high = $key-1;
		} elseif($v > $sortArr[$key]) {
			$low = $key+1;
		} else {
			return $key;
		}
	}
}

/**
 * 已经排序的数组,查到所有的keys = array_keys()
 * 使用递归的方式确认中间值
 */
function searchs($nums, $target, &$ret) {
    if (0 == count($nums)) {
        return;
    }
    $midIndex = ceil(count($nums)/2);
    if ($nums[$midIndex] < $target) {
        $nums = array_slice($nums, ++$midIndex);
        search($nums, $target, $ret);
    } elseif($nums[$midIndex] == $target) {
        $ret[] = $midIndex;
        for($index = $midIndex-1;$index>-1;$index--) {
            if ($nums[$index] == $target) {
                $ret[] = $index;
            } else {
                break;
            }

        }
        for($index = 1+$midIndex;$index<count($nums);$index++) {
            if ($nums[$index] == $target) {
                $ret[] = $index;
            } else {
                break;
            }
        }
    }else {
        $nums = array_slice($nums, 0, $midIndex-1);
        search($nums, $target, $ret);
    }
}

